"""
题目：https://leetcode-cn.com/problems/flatten-binary-tree-to-linked-list/
    给你二叉树的根结点 root ，请你将它展开为一个单链表：
    展开后的单链表应该同样使用 TreeNode ，其中 right 子指针指向链表中下一个结点，而左子指针始终为 null 。
    展开后的单链表应该与二叉树 先序遍历 顺序相同。
    示例 1：
    输入：root = [1,2,5,3,4,null,6]
    输出：[1,null,2,null,3,null,4,null,5,null,6]

思路：先按照前序排列获取该树的节点，再每次读取两个节点pre,cur，令pre.left=None,pre.right=cur来将树节点转换为链表。前序排列使用的是迭代方法。
时间复杂度：O(n)
空间复杂度：O(n)
"""
# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def flatten(self, root: TreeNode) -> None:
        """
        Do not return anything, modify root in-place instead.
        """
        preorder_list = self.preorder(root)
        size = len(preorder_list)
        for i in range(1,size):
            pre,cur = preorder_list[i - 1],preorder_list[i]
            pre.left = None
            pre.right = cur

    def preorder(self,root):
        res = []
        stack = []
        node = root
        while node or stack:
            while node:
                res.append(node)
                stack.append(node)
                node = node.left
            node = stack.pop()
            node = node.right
        return res
                
